package work.stackandqueque;

import java.util.Deque;
import java.util.LinkedList;

public class Problem239 {

    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> queue = new LinkedList<>();
        int n = nums.length;
        int[] ans = new int[n - k + 1];
        for (int i = 0; i < n; i++) {
            while (!queue.isEmpty() && nums[i] > nums[queue.getLast()]) {
                queue.removeLast();
            }
            queue.add(i);
            if (i - queue.getFirst() >= k) queue.removeFirst();
            if (i >= k - 1)
                ans[i - k + 1] = nums[queue.getFirst()];
        }
        return ans;
    }


    public static void main(String[] args) {
        Problem239 problem239 = new Problem239();
        int[] nums = {4, -2};
        int k = 2;
        int[] result = problem239.maxSlidingWindow(nums, k);
    }
}
